package practice1_100;

/**
 * 之前就刷过这道题，但是一直没通过，
 *         if(preRight==preLeft||inRight==inLeft) return new TreeNode(preorder[preLeft]);应该就是这里没写好逻辑
 *         当
 */
public class Offer07 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root= dp(preorder,inorder,0,preorder.length-1,0,preorder.length-1);
        return root;
    }
    public TreeNode dp(int[] preorder, int[] inorder,int preLeft,int preRight,int inLeft,int inRight){
        if(preRight<preLeft||inRight<inLeft) return null;
        //if(preRight==preLeft||inRight==inLeft) return new TreeNode(preorder[preLeft]);

        TreeNode root=new TreeNode(preorder[preLeft]) ;
        int i = inLeft;
        for (; i <=inRight ; i++) {
            if(inorder[i]==preorder[preLeft]) {
                break;
            }
        }
        root.left=dp(preorder,inorder,preLeft+1,preLeft+i-inLeft,inLeft,i-1);
        root.right=dp(preorder,inorder,preLeft+i-inLeft+1,preRight,i+1,inRight);
        return root;

    }

    public static void main(String[] args) {
        TreeNode a= new Offer07().buildTree(new int[]{3,9,20,15,7},new int[]{9,3,15,20,7});
        System.out.println(a);
    }
}
